/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.cf.code;

import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeBearer;
import com.android.dx.util.ExceptionWithContext;
import com.android.dx.util.Hex;
import com.android.dx.util.MutabilityControl;

/**
 * Representation of a Java method execution stack.
 * <p>
 * <b>Note:</b> For the most part, the documentation for this class ignores the
 * distinction between {@link Type} and {@link TypeBearer}.
 * </p>
 */
public final class ExecutionStack extends MutabilityControl {

	/** {@code non-null;} array of stack contents */
	private final TypeBearer[] stack;

	/**
	 * {@code non-null;} array specifying whether stack contents have entries in
	 * the local variable table
	 */
	private final boolean[] local;
	/**
	 * {@code >= 0;} stack pointer (points one past the end) / current stack
	 * size
	 */
	private int stackPtr;

	/**
	 * Constructs an instance.
	 * 
	 * @param maxStack
	 *            {@code >= 0;} the maximum size of the stack for this instance
	 */
	public ExecutionStack(int maxStack) {
		super(maxStack != 0);
		stack = new TypeBearer[maxStack];
		local = new boolean[maxStack];
		stackPtr = 0;
	}

	/**
	 * Makes and returns a mutable copy of this instance.
	 * 
	 * @return {@code non-null;} the copy
	 */
	public ExecutionStack copy() {
		ExecutionStack result = new ExecutionStack(stack.length);

		System.arraycopy(stack, 0, result.stack, 0, stack.length);
		System.arraycopy(local, 0, result.local, 0, local.length);
		result.stackPtr = stackPtr;

		return result;
	}

	/**
	 * Annotates (adds context to) the given exception with information about
	 * this instance.
	 * 
	 * @param ex
	 *            {@code non-null;} the exception to annotate
	 */
	public void annotate(ExceptionWithContext ex) {
		int limit = stackPtr - 1;

		for (int i = 0; i <= limit; i++) {
			String idx = (i == limit) ? "top0" : Hex.u2(limit - i);

			ex.addContext("stack[" + idx + "]: " + stackElementString(stack[i]));
		}
	}

	/**
	 * Replaces all the occurrences of the given uninitialized type in this
	 * stack with its initialized equivalent.
	 * 
	 * @param type
	 *            {@code non-null;} type to replace
	 */
	public void makeInitialized(Type type) {
		if (stackPtr == 0) {
			// We have to check for this before checking for immutability.
			return;
		}

		throwIfImmutable();

		Type initializedType = type.getInitializedType();

		for (int i = 0; i < stackPtr; i++) {
			if (stack[i] == type) {
				stack[i] = initializedType;
			}
		}
	}

	/**
	 * Gets the maximum stack size for this instance.
	 * 
	 * @return {@code >= 0;} the max stack size
	 */
	public int getMaxStack() {
		return stack.length;
	}

	/**
	 * Gets the current stack size.
	 * 
	 * @return {@code >= 0, < getMaxStack();} the current stack size
	 */
	public int size() {
		return stackPtr;
	}

	/**
	 * Clears the stack. (That is, this method pops everything off.)
	 */
	public void clear() {
		throwIfImmutable();

		for (int i = 0; i < stackPtr; i++) {
			stack[i] = null;
			local[i] = false;
		}

		stackPtr = 0;
	}

	/**
	 * Pushes a value of the given type onto the stack.
	 * 
	 * @param type
	 *            {@code non-null;} type of the value
	 * @throws SimException
	 *             thrown if there is insufficient room on the stack for the
	 *             value
	 */
	public void push(TypeBearer type) {
		throwIfImmutable();

		int category;

		try {
			type = type.getFrameType();
			category = type.getType().getCategory();
		} catch (NullPointerException ex) {
			// Elucidate the exception.
			throw new NullPointerException("type == null");
		}

		if ((stackPtr + category) > stack.length) {
			throwSimException("overflow");
			return;
		}

		if (category == 2) {
			stack[stackPtr] = null;
			stackPtr++;
		}

		stack[stackPtr] = type;
		stackPtr++;
	}

	/**
	 * Flags the next value pushed onto the stack as having local info.
	 */
	public void setLocal() {
		throwIfImmutable();

		local[stackPtr] = true;
	}

	/**
	 * Peeks at the {@code n}th element down from the top of the stack.
	 * {@code n == 0} means to peek at the top of the stack. Note that this will
	 * return {@code null} if the indicated element is the deeper half of a
	 * category-2 value.
	 * 
	 * @param n
	 *            {@code >= 0;} which element to peek at
	 * @return {@code null-ok;} the type of value stored at that element
	 * @throws SimException
	 *             thrown if {@code n >= size()}
	 */
	public TypeBearer peek(int n) {
		if (n < 0) {
			throw new IllegalArgumentException("n < 0");
		}

		if (n >= stackPtr) {
			return throwSimException("underflow");
		}

		return stack[stackPtr - n - 1];
	}

	/**
	 * Peeks at the {@code n}th element down from the top of the stack,
	 * returning whether or not it has local info.
	 * 
	 * @param n
	 *            {@code >= 0;} which element to peek at
	 * @return {@code true} if the value has local info, {@code false} otherwise
	 * @throws SimException
	 *             thrown if {@code n >= size()}
	 */
	public boolean peekLocal(int n) {
		if (n < 0) {
			throw new IllegalArgumentException("n < 0");
		}

		if (n >= stackPtr) {
			throw new SimException("stack: underflow");
		}

		return local[stackPtr - n - 1];
	}

	/**
	 * Peeks at the {@code n}th element down from the top of the stack,
	 * returning the type per se, as opposed to the <i>type-bearer</i>. This
	 * method is just a convenient shorthand for {@code peek(n).getType()}.
	 * 
	 * @see #peek
	 */
	public Type peekType(int n) {
		return peek(n).getType();
	}

	/**
	 * Pops the top element off of the stack.
	 * 
	 * @return {@code non-null;} the type formerly on the top of the stack
	 * @throws SimException
	 *             thrown if the stack is empty
	 */
	public TypeBearer pop() {
		throwIfImmutable();

		TypeBearer result = peek(0);

		stack[stackPtr - 1] = null;
		local[stackPtr - 1] = false;
		stackPtr -= result.getType().getCategory();

		return result;
	}

	/**
	 * Changes an element already on a stack. This method is useful in limited
	 * contexts, particularly when merging two instances. As such, it places the
	 * following restriction on its behavior: You may only replace values with
	 * other values of the same category.
	 * 
	 * @param n
	 *            {@code >= 0;} which element to change, where {@code 0} is the
	 *            top element of the stack
	 * @param type
	 *            {@code non-null;} type of the new value
	 * @throws SimException
	 *             thrown if {@code n >= size()} or the action is otherwise
	 *             prohibited
	 */
	public void change(int n, TypeBearer type) {
		throwIfImmutable();

		try {
			type = type.getFrameType();
		} catch (NullPointerException ex) {
			// Elucidate the exception.
			throw new NullPointerException("type == null");
		}

		int idx = stackPtr - n - 1;
		TypeBearer orig = stack[idx];

		if ((orig == null)
				|| (orig.getType().getCategory() != type.getType()
						.getCategory())) {
			throwSimException("incompatible substitution: "
					+ stackElementString(orig) + " -> "
					+ stackElementString(type));
		}

		stack[idx] = type;
	}

	/**
	 * Merges this stack with another stack. A new instance is returned if this
	 * merge results in a change. If no change results, this instance is
	 * returned. See {@link Merger#mergeStack(ExecutionStack,ExecutionStack)
	 * Merger.mergeStack()}
	 * 
	 * @param other
	 *            {@code non-null;} a stack to merge with
	 * @return {@code non-null;} the result of the merge
	 */
	public ExecutionStack merge(ExecutionStack other) {
		try {
			return Merger.mergeStack(this, other);
		} catch (SimException ex) {
			ex.addContext("underlay stack:");
			this.annotate(ex);
			ex.addContext("overlay stack:");
			other.annotate(ex);
			throw ex;
		}
	}

	/**
	 * Gets the string form for a stack element. This is the same as
	 * {@code toString()} except that {@code null} is converted to
	 * {@code "<invalid>"}.
	 * 
	 * @param type
	 *            {@code null-ok;} the stack element
	 * @return {@code non-null;} the string form
	 */
	private static String stackElementString(TypeBearer type) {
		if (type == null) {
			return "<invalid>";
		}

		return type.toString();
	}

	/**
	 * Throws a properly-formatted exception.
	 * 
	 * @param msg
	 *            {@code non-null;} useful message
	 * @return never (keeps compiler happy)
	 */
	private static TypeBearer throwSimException(String msg) {
		throw new SimException("stack: " + msg);
	}
}
